Typically, a digital image includes macroblocks distributed in lines and columns. Each line (or horizontal row) of the image includes, for example, macroblocks of 16×16 pixels. Conventionally, a macroblock is organised into four luma blocks and two, four or eight chroma blocks according to the type of sampling.
Traditionally, the coding or decoding of an image involves processing all of its macroblocks, sequentially, line by line, from left to right over a single line, and from top to bottom from one line to the next.
An embodiment of the invention applies in particular, but not exclusively, to the coding or decoding of a video sequence formed by a series of images. In this case, the coding or decoding technique is implemented in a video compression or decompression algorithm. It is thus consistent with a compression/decompression standard such as (this list is not exhaustive):                the H.263 standard, defined in the standardisation document as “ITU-T H.263”;        the H.263+ standard, defined in the standardisation document as “ITU-T H.263+”;        the H.264 standard (also referred to as H.26L or MPEG-4 AVC): defined in the standardisation document as “ISO MPEG-4 Part 10”;        the MPEG-4 Video standard: defined in the standardisation document as “ISO MPEG-4 Part 2”.        
It is, however, clear that an embodiment of the invention also applies to the coding or decoding of a fixed image.
An embodiment of the invention can also apply wherever there is a spatial dependence context for the processing of macroblocks of an image. In other words, it is assumed that to process each macroblock of the image, it is necessary to know the result of the previous processing of other macroblocks of the same image.
Such a spatial dependence context exists in particular, but not exclusively, in the methods for coding or decoding consistent with the aforementioned compression/decompression standards based on a motion estimation. FIG. 1 shows the spatial dependence context as defined in these standards. To process a given macroblock MB, it is necessary to know the result of the processing of the left macroblock (MBG), that of the upper macroblock (MBH) and that of the right macroblock (MBD).
The processing of all of the macroblocks of an image by a single processor does not appear to be optimal in terms of computing time.
In addition, a multithreading technique is known, which involves optimally distributing (i.e. multithreading) the computing loads for processing over a plurality of available processors.
This known technique is used in the field of video compression, according to either a general approach or a narrow approach.
The general approach includes distributing macro-tasks over each of the processors. For example, it is assumed that the coding of an image requires three tasks A, B and C to be executed which must be ordered as follows: A, then B, then C. It can then be imagined that to best distribute the tasks A, B and C over two processors, two threads T1 and T2 are created, with T1 managing only tasks A ad B and T2 managing only task C. This multithreading can be carried out only if T1 can work on image N while T2 works on image N−1, with N being the number of the image of a video sequence. It can be seen that this distribution is optimal only if the load used by tasks A and B is substantially equivalent to that used by task C (isodistribution of loads between processors).
A disadvantage of the multithreading technique according to the general approach is that the isodistribution of the loads between processors is almost never verified in practice. In other words, it is very difficult, and even impossible in some cases, to find a perfect balance by separating entire tasks from one another.
Another disadvantage of the multithreading technique according to the general approach is that it requires a specific implementation of the calling program, with the use of a stacking mechanism.
Yet another disadvantage of the multithreading technique according to the general approach is that it cannot be applied in the case of a spatial dependence context as described above.
The narrow approach includes separating each task into as many basic tasks as can be executed simultaneously by a plurality of processors, when possible. For example, in the field of video compression or image compression (with the aforementioned conventional sequential processing order: line by line, from left to right over the same line, and from top to bottom from one line to the next), the image can be separated into N horizontal bands and have each of them processed by one of N processors. In this case, it is not necessary for the different threads to be mutually synchronised. They must simply inform a main thread when they have completed their processing. This provides a very balanced distribution of loads between processors.
However, a major disadvantage of the multithreading technique according to the narrow approach is that it cannot be applied in the case of a spatial dependence context as described above. Indeed, in this context, each first line of a given horizontal band (lower band) of the image cannot be processed as long as the last line of the horizontal band located above (upper band) has not been processed. The processors could therefore only act in series and not simultaneously, which counteracts any benefit of the use of this technique in this context.